package xyz.scootaloo.oj.offer

import org.junit.Test
import xyz.scootaloo.oj.ds.TreeNode
import xyz.scootaloo.oj.ds.helper.CollectionBuilder

/**
 * @author flutterdash@qq.com
 * @since 2021/4/11 9:16
 */
class P32II {

    private fun levelOrder(root: TreeNode?): List<List<Int>> {
        val res = ArrayList<ArrayList<Int>>()
        if (root == null) return res
        val deque = ArrayDeque<TreeNode>()
        deque.addLast(root)

        var count = 1
        while (!deque.isEmpty()) {
            val level = ArrayList<Int>()
            var nextCount = 0
            for (c in 1..count) {
                val node = deque.removeFirst()
                level.add(node.`val`)
                if (node.left != null) {
                    deque.addLast(node.left)
                    nextCount++
                }
                if (node.right != null) {
                    deque.addLast(node.right)
                    nextCount++
                }
            }
            count = nextCount
            res.add(level)
        }

        return res
    }

    @Test
    fun test0() {
        val root = CollectionBuilder.initTree()
            .setRoot(3)
            .addLevel(9, 20)
            .addLevel(null, null, 15, 7)
            .build()
        println(levelOrder(root))
    }

}
